package 简单;

/*
* 数组的相对排序
* 力扣地址：https://leetcode-cn.com/problems/relative-sort-array/
* 给你两个数组，arr1 和 arr2，
*    arr2 中的元素各不相同
*    arr2 中的每个元素都出现在 arr1 中
* 对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。
* 未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
* 示例：
* 输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
* 输出：[2,2,2,1,4,3,3,9,6,7,19]
*
* */

import java.util.*;

public class demo1122 {

    public static void main(String[] args) {

        int[] a = {2,3,1,3,2,4,6,7,9,2,19};
        int[] b = {2,1,4,3,9,6};

        System.out.println(Arrays.toString(relativeSortArray2(a,b)));
    }

    //第一版
    public static int[] relativeSortArray(int[] arr1, int[] arr2) {

        HashMap<Integer,Integer> map = new HashMap<>();

        for (int i=0;i<arr1.length;i++){

            if(map.get(arr1[i])!=null)
            {
                map.put(arr1[i],map.get(arr1[i])+1);
            }
            else
            {
                map.put(arr1[i],1);
            }

        }

        int count = 0;
        for (int i=0;i<arr2.length;i++){

//            System.out.println(map.get(arr2[i]));
            for (int j=0;j<map.get(arr2[i]);j++)
            {
                arr1[count++] = arr2[i];
            }
            map.remove(arr2[i]);
        }

        Set<Integer> integers = map.keySet();
        Iterator<Integer> iterator = integers.iterator();
        int[] ts = new int[arr1.length-count];

        int t=0;
        while (iterator.hasNext()){
            int m = iterator.next();

            for (int i=0;i<map.get(m);i++)
                ts[t++] = m;
            iterator.remove();

        }

        Arrays.sort(ts);

//        System.out.println(Arrays.toString(ts));

        for (int i=count;i<arr1.length;i++){
            arr1[i] = ts[i-count];
        }

        return arr1;

    }

    //尝试了优化一点点
    public static int[] relativeSortArray2(int[] arr1, int[] arr2) {

        Arrays.sort(arr1);
        int[] ts = new int[arr1.length];

        int count = 0;
        for (int i=0;i<arr2.length;i++) {

            int st = getz(arr1, arr2[i]);

            while (st != -1)
            {
                ts[count++] = arr2[i];
//                System.out.println(st);
                arr1[st] = -1;
//                System.out.println(Arrays.toString(arr1));
                st = getz(arr1, arr2[i]);

            }

        }

        Arrays.sort(arr1);

       for (int i = count;i<arr1.length;i++){
           ts[i] = arr1[i];
       }

        return ts;

    }

    static int getz(int[] a,int n){

        for (int i=0;i<a.length;i++){

            if (a[i] == n)
            {
                return i;
            }

        }

        return -1;

    }



}
